package hwFour1;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class CC {
    private boolean[] marked;   // 标记顶点是否被访问
    private int[] id;           // 连通分量的 id
    private int count;          // 连通分量的数量

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        count = 0; // 初始化连通分量计数
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v); // 对每个未访问的顶点调用 dfs
                count++;   // 每完成一次 dfs，说明发现了一个新的连通分量
            }
        }
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        id[v] = count; // 当前顶点属于当前的连通分量
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w); // 递归访问所有未访问的邻接顶点
            }
        }
    }

    public int count() {
        return count;
    }

    public int id(int v) {
        return id[v];
    }
    public static void main(String[] args) throws FileNotFoundException {
        // 从文件读取图
        Scanner in = new Scanner(new File("hwFour1/tinyGex2.txt"));
        Graph G = new Graph(in);

        // 计算连通分量
        CC cc = new CC(G);

        // 按连通分量的 id 分类顶点
        int M = cc.count(); // 连通分量的数量
        System.out.println(M + " 个连通分量：");

        List<Integer>[] components = (List<Integer>[]) new List[M];
        for (int i = 0; i < M; i++) {
            components[i] = new ArrayList<>();
        }

        for (int v = 0; v < G.V(); v++) {
            components[cc.id(v)].add(v);
        }

        // 打印每个连通分量
        for (int i = 0; i < M; i++) {
            System.out.print("连通分量 " + (i + 1) + ": ");
            for (int v : components[i]) {
                System.out.print(v + " ");
            }
            System.out.println();
        }
    }

}